package JZOffer;

public class Jz33 {

    // Jz33.二叉搜索树的后序遍历序列
    public boolean verifyPostorder(int[] postorder) {

//        if (postorder == null || postorder.length == 0) {
//            return false;
//        }
//
//        int root = postorder[postorder.length - 1];
//
//        // 获取第一个大于根节点的下标，得到左右子树的边界
//        int i = 0;
//        for (; i < postorder.length - 1; i++) {
//            if (postorder[i] > root) break;
//        }
//        // 判断右子树中的节点是否都大于根节点
//        int j = i;
//        for (; j < postorder.length - 1; j++) {
//            if (postorder[j] < root) return false;
//        }

        return res(postorder, 0, postorder.length - 1);

    }

    boolean res(int[] postorder, int i, int j) {
        if (i >= j) return true;
        int p = i;
        while (postorder[p] < postorder[j]) p++;
        int m = p;
        while (postorder[p] > postorder[j]) p++;
        return p == j && res(postorder, i, m - 1) && res(postorder, m, j - 1);
    }

}
